package com.yanceysong.codetop.s31_s40;

import com.yanceysong.common.TreeNode;

import java.util.*;

public class S39_Mid_199_二叉树的右视图 {
    /**
     * 题目：二叉树的右视图 (Binary Tree Right Side View)
     * LeetCode: <a href="https://leetcode.cn/problems/binary-tree-right-side-view/">...</a>
     * 难度：中等
     * ------------------------------------------------------------
     * 描述：
     * 给定一个二叉树的根节点 root。想象你站在它的右侧，从上到下，返回你能看到的每一层最右侧节点的值。
     * <p>
     * 示例：
     * 输入：root = [1,2,3,null,5,null,4]
     * .           1
     * .         /   \
     * .        2     3
     * .         \     \
     * .          5     4
     * .输出：[1,3,4]
     * .解释：
     * .层序：
     * . Level 0 -> 1   -> 最右 1
     * . Level 1 -> 2 3 -> 最右 3
     * . Level 2 -> 5 4 -> 最右 4
     * <p>
     * 边界示例：
     * 1. root = []           -> []
     * 2. root = [1]          -> [1]
     * 3. root = [1,2]        -> [1,2]
     * 4. root = [1,null,2]   -> [1,2]
     * <p>
     * ------------------------------------------------------------
     * 思路一（层序遍历 BFS）：
     * 按层遍历，记录每一层的最后一个节点。可通过循环 size 控制一层范围。
     * 关键：进入内层 for 时 queue 中正好是当前层所有节点；索引到该层最后一个节点时加入答案。
     * <p>
     * ASCII 层序示意：
     * .  Queue 层处理过程 (示例树)：
     * .  [1]
     * .  -> 处理层0: 弹出 1, 其子节点 2,3 入队, 该层最后一个是 1 -> res=[1]
     * .  [2,3]
     * .  -> 处理层1: 依次弹出 2,3, 子 5,4 入队, 最后一个是 3 -> res=[1,3]
     * .  [5,4]
     * .  -> 处理层2: 依次弹出 5,4, 最后一个是 4 -> res=[1,3,4]
     * <p>
     * 时间复杂度：O(N)  N 为节点数，每个节点仅入队/出队一次。
     * 空间复杂度：O(W)  W 为树的最大宽度（队列所需空间）。最坏 O(N)。
     * <p>
     * ------------------------------------------------------------
     * 思路二（DFS 先右后左）：
     * 使用前序遍历，访问顺序：根 -> 右 -> 左。首次到达某深度 depth 时，当前节点必为该层最右结点。
     * 只要 results.size() == depth 时记录该节点。
     * 时间复杂度：O(N)
     * 空间复杂度：O(H)  递归栈高度，H 为树高，最坏 O(N)，平衡树 O(logN)。
     * <p>
     * 关键洞察：
     * 1. "右视图" == 每层最右 -> 与层的概念强相关，可 BFS。
     * 2. 也可利用遍历顺序控制（右优先 DFS），借助“第一次到达该深度”的特性。
     * 3. BFS 更直观，DFS 更精简（无需存储整层）。
     * <p>
     * 选择理由：主函数默认使用 BFS，便于对层的理解；提供 DFS 备选以拓展思维。
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> rightViewList = new ArrayList<>();   // 保存每一层最右节点值
        Deque<TreeNode> levelQueue = new LinkedList<>();   // 层序队列
        if (root != null) levelQueue.offer(root);

        while (!levelQueue.isEmpty()) {
            int nodesInThisLevel = levelQueue.size(); // 当前层节点数量快照
            for (int i = 0; i < nodesInThisLevel; i++) {
                TreeNode current = levelQueue.poll(); // 取出当前层节点
                if (current == null) continue;         // 保护性判断
                // 若是该层最后一个节点（i == nodesInThisLevel-1） -> 加入结果
                if (i == nodesInThisLevel - 1) {
                    rightViewList.add(current.val);
                }
                // 先左后右入队（顺序无强制要求，因为我们用 i==last 识别最右）
                if (current.left != null) levelQueue.offer(current.left);
                if (current.right != null) levelQueue.offer(current.right);
            }
        }
        return rightViewList;
    }

    /**
     * DFS 右优先版本：
     * 访问顺序 root -> right -> left，保证第一次抵达的深度节点是该层最右。
     */
    public List<Integer> rightSideViewDFS(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfsRightFirst(root, 0, result);
        return result;
    }

    private void dfsRightFirst(TreeNode node, int depth, List<Integer> results) {
        if (node == null) return;
        // 第一次到达该深度，记录节点值
        if (results.size() == depth) {
            results.add(node.val);
        }
        // 右优先遍历
        dfsRightFirst(node.right, depth + 1, results);
        dfsRightFirst(node.left, depth + 1, results);
    }

    // ====================== 测试代码区域 (main) ======================
    public static void main(String[] args) {
        S39_Mid_199_二叉树的右视图 solver = new S39_Mid_199_二叉树的右视图();
        System.out.println("=== 二叉树右视图 测试开始 ===");

        // 测试1：题目示例
        System.out.println("\n--- 测试1: 题目示例 ---");
        testExample(solver);

        // 测试2：单节点
        System.out.println("\n--- 测试2: 单节点 ---");
        testSingleNode(solver);

        // 测试3：左斜树
        System.out.println("\n--- 测试3: 左斜树 ---");
        testLeftSkewed(solver);

        // 测试4：右斜树
        System.out.println("\n--- 测试4: 右斜树 ---");
        testRightSkewed(solver);

        // 测试5：完全二叉树
        System.out.println("\n--- 测试5: 完全二叉树 ---");
        testCompleteTree(solver);

        // 测试6：交错结构（锯齿/zigzag）
        System.out.println("\n--- 测试6: Zigzag 结构 ---");
        testZigzag(solver);

        // 测试7：空树
        System.out.println("\n--- 测试7: 空树 ---");
        testEmptyTree(solver);

        // 测试8：随机多次（结构验证 BFS 与 DFS 一致）
        System.out.println("\n--- 测试8: BFS 与 DFS 输出一致性随机校验 ---");
        randomConsistencyCheck(solver, 50, 10);

        System.out.println("\n=== 所有测试完成 ===");
    }

    // ========== 构建与测试辅助函数 ==========

    /**
     * 根据层序数组（Integer，null 表示空）构建二叉树。
     */
    private static TreeNode buildTreeLevelOrder(Integer[] arr) {
        if (arr == null || arr.length == 0 || arr[0] == null) return null;
        TreeNode root = new TreeNode(arr[0]);
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int index = 1;
        while (!queue.isEmpty() && index < arr.length) {
            TreeNode current = queue.poll();
            if (current == null) continue;
            // 左子
            if (index < arr.length && arr[index] != null) {
                current.left = new TreeNode(arr[index]);
                queue.offer(current.left);
            }
            index++;
            // 右子
            if (index < arr.length && arr[index] != null) {
                current.right = new TreeNode(arr[index]);
                queue.offer(current.right);
            }
            index++;
        }
        return root;
    }

    private static void assertListEquals(List<Integer> actual, List<Integer> expected, String message) {
        if (!actual.equals(expected)) {
            throw new AssertionError(message + " | actual=" + actual + ", expected=" + expected);
        }
    }

    // ========== 各独立测试用例 ==========
    private static void testExample(S39_Mid_199_二叉树的右视图 solver) {
        TreeNode root = buildTreeLevelOrder(new Integer[]{1, 2, 3, null, 5, null, 4});
        List<Integer> bfs = solver.rightSideView(root);
        List<Integer> dfs = solver.rightSideViewDFS(root);
        System.out.println("示例树右视图 BFS: " + bfs + ", DFS: " + dfs);
        List<Integer> expected = Arrays.asList(1, 3, 4);
        assertListEquals(bfs, expected, "示例 BFS 结果错误");
        assertListEquals(dfs, expected, "示例 DFS 结果错误");
        System.out.println("✓ 示例测试通过");
    }

    private static void testSingleNode(S39_Mid_199_二叉树的右视图 solver) {
        TreeNode root = new TreeNode(42);
        List<Integer> expected = Collections.singletonList(42);
        assertListEquals(solver.rightSideView(root), expected, "单节点 BFS 错误");
        assertListEquals(solver.rightSideViewDFS(root), expected, "单节点 DFS 错误");
        System.out.println("✓ 单节点测试通过");
    }

    private static void testLeftSkewed(S39_Mid_199_二叉树的右视图 solver) {
        // 形状： 1 -> 2 -> 3 -> 4 (全左)
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.left.left = new TreeNode(4);
        List<Integer> expected = Arrays.asList(1, 2, 3, 4); // 每层只有一个节点
        assertListEquals(solver.rightSideView(root), expected, "左斜 BFS 错误");
        assertListEquals(solver.rightSideViewDFS(root), expected, "左斜 DFS 错误");
        System.out.println("✓ 左斜树测试通过");
    }

    private static void testRightSkewed(S39_Mid_199_二叉树的右视图 solver) {
        // 形状：1 -> 2 -> 3 -> 4 (全右)
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);
        root.right.right.right = new TreeNode(4);
        List<Integer> expected = Arrays.asList(1, 2, 3, 4);
        assertListEquals(solver.rightSideView(root), expected, "右斜 BFS 错误");
        assertListEquals(solver.rightSideViewDFS(root), expected, "右斜 DFS 错误");
        System.out.println("✓ 右斜树测试通过");
    }

    private static void testCompleteTree(S39_Mid_199_二叉树的右视图 solver) {
        // 完全二叉树：        1
        //                 /   \
        //                2     3
        //               / \   / \
        //              4  5  6  7
        TreeNode root = buildTreeLevelOrder(new Integer[]{1, 2, 3, 4, 5, 6, 7});
        List<Integer> expected = Arrays.asList(1, 3, 7);
        assertListEquals(solver.rightSideView(root), expected, "完全树 BFS 错误");
        assertListEquals(solver.rightSideViewDFS(root), expected, "完全树 DFS 错误");
        System.out.println("✓ 完全二叉树测试通过");
    }

    private static void testZigzag(S39_Mid_199_二叉树的右视图 solver) {
        // 构造交错: 1
        //        / \
        //       2   3
        //        \   \
        //         5   4
        //        /
        //       6
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(4);
        root.left.right.left = new TreeNode(6);
        List<Integer> expected = Arrays.asList(1, 3, 4, 6);
        assertListEquals(solver.rightSideView(root), expected, "Zigzag BFS 错误");
        assertListEquals(solver.rightSideViewDFS(root), expected, "Zigzag DFS 错误");
        System.out.println("✓ Zigzag 结构测试通过");
    }

    private static void testEmptyTree(S39_Mid_199_二叉树的右视图 solver) {
        TreeNode root = null;
        List<Integer> expected = Collections.emptyList();
        assertListEquals(solver.rightSideView(root), expected, "空树 BFS 错误");
        assertListEquals(solver.rightSideViewDFS(root), expected, "空树 DFS 错误");
        System.out.println("✓ 空树测试通过");
    }

    private static void randomConsistencyCheck(S39_Mid_199_二叉树的右视图 solver, int rounds, int maxNodes) {
        Random random = new Random(12345);
        for (int r = 1; r <= rounds; r++) {
            // 随机生成节点数量 (0..maxNodes)
            int n = random.nextInt(maxNodes + 1);
            Integer[] arr = new Integer[n];
            for (int i = 0; i < n; i++) {
                // 以一定概率生成 null 形成稀疏结构（根节点不置空）
                if (i == 0) {
                    arr[i] = random.nextInt(50);
                } else {
                    arr[i] = random.nextDouble() < 0.25 ? null : random.nextInt(50);
                }
            }
            TreeNode root = buildTreeLevelOrder(arr);
            List<Integer> bfs = solver.rightSideView(root);
            List<Integer> dfs = solver.rightSideViewDFS(root);
            if (!bfs.equals(dfs)) {
                throw new AssertionError("第" + r + "轮随机一致性失败: BFS=" + bfs + ", DFS=" + dfs + ", tree=" + Arrays.toString(arr));
            }
        }
        System.out.println("随机一致性校验通过，共 " + rounds + " 轮");
    }
}
